package JZOffer;

import java.util.Arrays;

/**
 * @author Lw中
 * @date 2021/9/5 17:51
 */
public class Jz40 {

    // Jz40.最小的k个数
    public int[] getLeastNumbers(int[] arr, int k) {

        // 方法一：使用排序(可使用快速排序、归并排序、选择排序进行Java自带函数的代替)
//        Arrays.sort(arr);
//        int[] nums = new int[k];
//        for (int i = 0; i < k; i++) {
//            nums[i] = arr[i];
//        }
//        return nums;

        // 基于快速排序的数组划分
        /**
         * LWZ TODO : 2021/9/5 快速排序写的不够熟练
         *
         */
        if (k >= arr.length) return arr;
        return quickSort(arr, k, 0, arr.length - 1);

    }
    private int[] quickSort(int[] arr, int k, int l, int r) {
        int i = l, j = r;
        while (i < j) {
            while (i < j && arr[j] >= arr[l]) j--;
            while (i < j && arr[i] <= arr[l]) i++;
            swap(arr, i, j);
        }
        swap(arr, i, l);
        if (i > k) return quickSort(arr, k, l, i - 1);
        if (i < k) return quickSort(arr, k, i + 1, r);
        return Arrays.copyOf(arr, k);
    }
    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

}
